#ifndef STATICLIST_H
#define STATICLIST_H

#include <iostream>
using namespace std;

#define MAXSIZE 100

template<typename T>
struct StaticNode {
    T data;
    int next;
};

template<typename T>
class StaticList {
private:
    StaticNode<T> nodes[MAXSIZE];
    int head;
    int length;
    int freeList;

    void initialize() {
        for (int i = 0; i < MAXSIZE - 1; i++) {
            nodes[i].next = i + 1;
        }
        nodes[MAXSIZE - 1].next = -1;
        freeList = 0;
        
        head = -1;
        length = 0;
    }

    int allocateNode() {
        if (freeList == -1) {
            return -1;
        }
        int index = freeList;
        freeList = nodes[freeList].next;
        return index;
    }

    void freeNode(int index) {
        nodes[index].next = freeList;
        freeList = index;
    }

public:
    StaticList() {
        initialize();
    }

    ~StaticList() {}

    void createList(const T arr[], int n) {
        clear();
        
        if (n == 0) return;
        
        head = allocateNode();
        if (head == -1) {
            cout << "空间不足，无法创建链表！" << endl;
            return;
        }
        
        nodes[head].data = arr[0];
        nodes[head].next = -1;
        length = 1;
        
        int current = head;
        
        for (int i = 1; i < n; i++) {
            int newNode = allocateNode();
            if (newNode == -1) {
                cout << "空间不足，只创建了部分链表！" << endl;
                break;
            }
            
            nodes[newNode].data = arr[i];
            nodes[newNode].next = -1;
            nodes[current].next = newNode;
            current = newNode;
            length++;
        }
        
        cout << "静态链表创建完成，长度: " << length << endl;
    }

    void display() const {
        if (head == -1) {
            cout << "静态链表为空！" << endl;
            return;
        }
        
        cout << "静态链表: ";
        int current = head;
        while (current != -1) {
            cout << nodes[current].data;
            if (nodes[current].next != -1) {
                cout << " -> ";
            }
            current = nodes[current].next;
        }
        cout << " -> NULL" << endl;
        
        cout << "内部结构: [";
        current = head;
        while (current != -1) {
            cout << "(" << nodes[current].data << "," << nodes[current].next << ")";
            if (nodes[current].next != -1) {
                cout << "->";
            }
            current = nodes[current].next;
        }
        cout << "]" << endl;
    }

    void clear() {
        int current = head;
        while (current != -1) {
            int nextNode = nodes[current].next;
            freeNode(current);
            current = nextNode;
        }
        head = -1;
        length = 0;
    }

    int getLength() const {
        return length;
    }

    bool isEmpty() const {
        return head == -1;
    }

    void rightShift(int n) {
        if (isEmpty()) {
            cout << "静态链表为空，无法右移！" << endl;
            return;
        }
        
        if (n % length == 0) {
            cout << "移动位数为长度的整数倍，链表保持不变" << endl;
            return;
        }
        
        n = n % length;
        
        if (n < 0) {
            cout << "移动位数不能为负数！" << endl;
            return;
        }
        
        if (n == 0) {
            return;
        }
        
        int steps = length - n - 1;
        int newTail = head;
        for (int i = 0; i < steps; i++) {
            newTail = nodes[newTail].next;
        }
        
        int oldTail = newTail;
        while (nodes[oldTail].next != -1) {
            oldTail = nodes[oldTail].next;
        }
        
        int newHead = nodes[newTail].next;
        nodes[oldTail].next = head;
        nodes[newTail].next = -1;
        head = newHead;
        
        cout << "静态链表已右移 " << n << " 位" << endl;
    }

    void toArray(T arr[]) const {
        int current = head;
        int index = 0;
        while (current != -1) {
            arr[index++] = nodes[current].data;
            current = nodes[current].next;
        }
    }
};

#endif